//给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,3]
//输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
// 
//
// 示例 2： 
//
// 
//输入：nums = [0,1]
//输出：[[0,1],[1,0]]
// 
//
// 示例 3： 
//
// 
//输入：nums = [1]
//输出：[[1]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 6 
// -10 <= nums[i] <= 10 
// nums 中的所有整数 互不相同 
// 
// Related Topics 数组 回溯 
// 👍 1577 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
var result [][]int
func permute(nums []int) [][]int {

    result = make([][]int, 0)

    track := make([]int, 0, len(nums))
    used :=  make([]bool, len(nums))  // 直接访问i 必须空间申请出来

    backtrack(nums, track, used)

    return result
}

func backtrack(nums []int, track []int, used []bool){
    if len(nums) == len(track) {
        tmp := make([]int, len(track)) // cap的空间不能直接使用
        copy(tmp, track)  // 深拷贝

        result = append(result, tmp)
        return
    }

    for i := 0; i < len(nums); i++ {
        if used[i] {
            continue
        }

        // 做选择
        track = append(track, nums[i])
        used[i] = true

        backtrack(nums, track, used)

        // 撤销选择
        track = track[:len(track) - 1]
        used[i] = false
    }
}
//leetcode submit region end(Prohibit modification and deletion)
